package code;

/*
 * 
To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

import java.util.*;

/**
 *
 * @author jyotesh
 */
public class Kruskal {
    
    class Node {
        private int nodeIndex;
        private Node parent;
        private int rank;
        
        Node(int nodeIndex) {
            this.nodeIndex = nodeIndex;
        }
        
        public void setParent(Node parent) {
            this.parent = parent;
        }
        
        public void setRank(int rank) {
            this.rank = rank;
        }
        
        public int getNodeIndex() {
            return this.nodeIndex;
        }
        
        public Node getParent() {
            return this.parent;
        }
        
        public int getRank() {
            return this.rank;
        }
    }
    
    class Edge {
        private Node node1;
        private Node node2;
        private int weight;
        
        Edge(Node node1, Node node2, int weight) {
            this.node1 = node1;
            this.node2 = node2;
            this.weight = weight;
        }
        
        public Node getNode1() {
            return this.node1;
        }
        
        public Node getNode2() {
            return this.node2;
        }
        
        public int getWeight() {
            return this.weight;
        }
    }
    
    class EdgeComparator implements Comparator {

        @Override
        public int compare(Object o1, Object o2) {
            int weight1 = ((Edge)o1).getWeight();
            int weight2 = ((Edge)o2).getWeight();
            if (weight1 < weight2)
                return 1;
            else if (weight1 > weight2)
                return -1;
            else
                return 0;
        }
        
    }
    
    private int[][] adjacencyWeights = null;
    
    Kruskal(int[][] adjacencyWeights) {
        this.adjacencyWeights = adjacencyWeights;
    }
    
    public int[][] mst() {
        ArrayList<Edge> tree = new ArrayList<Edge>();
        Node[] nodeList = new Node[adjacencyWeights.length];
        ArrayList<Edge> edgeList = new ArrayList<Edge>();
        for (int i = 0; i < adjacencyWeights.length; i++) {
            nodeList[i] = new Node(i);
            makeSet(nodeList[i]);
        }
        for (int i = 0; i < adjacencyWeights.length; i++)
            for (int j = i + 1; j < adjacencyWeights.length; j++)
                if (adjacencyWeights[i][j] != 0)
                    edgeList.add(new Edge(nodeList[i], nodeList[j], adjacencyWeights[i][j]));
        Collections.sort(edgeList, new EdgeComparator());
        for (int i = 0; i < edgeList.size(); i++) {
            if (findSet(edgeList.get(i).getNode1()).getNodeIndex() != findSet(edgeList.get(i).getNode2()).getNodeIndex()) {
                tree.add(edgeList.get(i));
                union(edgeList.get(i).getNode1(), edgeList.get(i).getNode2());
            }
        }
        for (int i = 0; i < adjacencyWeights.length; i++)
            for (int j = 0; j < adjacencyWeights.length; j++)
                adjacencyWeights[i][j] = 0;
        for (int i = 0; i < tree.size(); i++) {
            adjacencyWeights[tree.get(i).getNode1().getNodeIndex()][tree.get(i).getNode2().getNodeIndex()] = tree.get(i).getWeight();
            adjacencyWeights[tree.get(i).getNode2().getNodeIndex()][tree.get(i).getNode1().getNodeIndex()] = tree.get(i).getWeight();
        }
        return adjacencyWeights;
    }
    
    private void makeSet(Node node) {
        node.setParent(node);
        node.setRank(0);
    }
    
    private Node findSet(Node node) {
        if (node.getNodeIndex() != node.getParent().getNodeIndex())
            node.setParent(findSet(node.getParent()));
        return node.getParent();
    }
    
    private void union(Node node1, Node node2) {
        link(findSet(node1), findSet(node2));
    }
    
    private void link(Node node1, Node node2) {
        if (node1.getRank() > node2.getRank())
            node2.setParent(node1);
        else {
            node1.setParent(node2);
            if (node1.getRank() == node2.getRank())
                node2.setRank(node2.getRank() + 1);
        }
    }
}
